1. Field of the Invention
The present invention relates to an alignment method for a three-dimensional (3D) object, for aligning plural surface shapes acquired by measuring the three-dimensional object from plural different directions, and an apparatus therefor.
The present invention also relates to a unifying method for three-dimensional shape data, for aligning plural surface shapes acquired as mentioned above, as shape data utilizing plural triangular patches, thereby unifying these data into single three-dimensional shape data, and an apparatus therefor.
The present invention also relates to an information processing apparatus capable, in the unifying process for the above-mentioned surface shapes, of unifying plural hierarchic geometrical shape data utilizing polygon patches, into a single hierarchic geometrical shape data, and a method therefor.
2. Related Background Art
There has been developed technology for entering the three-dimensional shape data of an object, utilizing for example an image input apparatus capable of entering a distanced image. The input of such distanced image has been achieved, for example, by:
(1) light wave distance measurement for measuring the light flight time by time measurement or phase measurement and determining the distance to the object from the time required by the light to reach the object and return therefrom; or PA1 (2) trigonometric distance measurement by taking a scene from different angles with plural cameras and determining the corresponding points in the images taken by the cameras; or PA1 (3) trigonometric measurement utilizing a camera and a projector for projecting a light pattern [S. Iguchi et al., Optoelectronics (1985), No. 12, pp.59] PA1 translation means for translating the shape data of respective hierarchic levels of said plural hierarchic three-dimensional shape data to a positional relationship for unification; PA1 setting means for selecting two shape data from the shape data after translation by said translation means and setting a section plane constituting the boundary plane after the unification of the two; PA1 division means for dividing each of the two shape data by the section plane and forming gap areas on both sides of the section plane, in portions to be used for unifying thus divided shape data; PA1 unification means for generating polygon patches in the gap areas thereby unifying the two shape data; PA1 first control means for causing the unification means to effect unification of the shape data on all the plural hierarchic three-dimensional shape data; and PA1 second control means for causing the first control means to effect unification on all the hierarchic levels of the plural hierarchic three-dimensional shape data, utilizing the results of translation by the translation means and the section planes. PA1 Also the above-mentioned objects can be attained, according to the present invention, by another information processing apparatus for processing plural three-dimensional shape data, comprising: PA1 translation means for translating the three-dimensional shape data to be unified into a positional relationship in a unified state; PA1 setting means for setting, for two shape data after translation by said translation means, a section plane constituting the boundary plane of the unification of the two: PA1 translation means for translating the three-dimensional shape data to be unified to a positional relationship in unified state; PA1 setting means for setting, for two shape data after translation by the translation means, a section plane constituting a boundary plane for the unification of the two; PA1 division means for dividing each of the two shape data by the section plane, and forming gap areas on both sides of the section plane between the partial shapes to be used for unification of thus divided shape data; PA1 extraction means for extracting vertexes constituting the gap areas in the partial shapes to be used for unification of the shape data and vertexes contained in the partial shapes, among those of the aperture contained in the shape data; PA1 unification means for generating, utilizing the vertexes extracted by the extraction means, polygon patches in the gap areas, thereby unifying the two shape data.
The shape data of an object are generated from thus entered data of the distanced image, by preparing normal line vectors of plural resolutions, then preparing plural edge map data from the distanced image data and the normal line vectors thereby generating polygon data of plural sizes, and generating triangular patches by dividing the polygon data into triangles.
It is also proposed to prepare a three-dimensional geometrical model, based on thus entered distanced image data, by approximating the surface shape of the three-dimensional object with small planar patches (for example as disclosed in the U.S. patent application Ser. No.08/300,997).
It is in general possible to more precisely express the surface irregularities of the three-dimensional shape by employing a larger number of planar patches of smaller areas, but, in the computer processing of the three-dimensional data, the amount of processing can be reduced with a smaller number of patches. It is therefore generally practiced to prepare plural three-dimensional shape data, different in the precision of shape expression, and to suitably switch these shape data according to the processing ability of the computer or the operation status of the application. The level of such precision of the shape expression will be defined as a "hierarchy", and the shape data of plural hierarchic levels will be collectively called "hierarchic three-dimensional shape data". There is already proposed a method of preparing such hierarchic three-dimensional data (for example as disclosed in the U.S. patent application Ser. No.08/300,997).
Also for displaying such distanced image, there is known a method of displaying an image of the three-dimensional object, seen from an arbitrary direction of line of sight, and changing the direction of line of sight with a suitable device such as a mouse or a keyboard.
However, as the above-mentioned distanced image input apparatus utilizes two-dimensional (2D) optical scanning based on a rotating mirror or a fixed camera, the measurement of the rear side, upper face or bottom of the object is not possible. For acquiring the three-dimensional shape data of the object from all the directions, it is necessary to unify the surface shape data of the object measured from plural directions. Since the surface shapes acquired from different directions of measurement generally have respectively different three-dimensional coordinate systems, it becomes necessary, in unifying the plural surface shape data, to effect alignment for determining the positional relationship among the surface shapes.
For aligning the plural surface shapes of the three-dimensional object, there can be utilized the above-mentioned display method according to the direction of line of sight. More specifically the alignment is conducted by displaying an image, obtained by projecting the surface shapes onto a known plane in the three-dimensional space, and manually adjusting the position and the direction of one or plural surface shapes in the three-dimensional space, while watching the displayed image, so as that the same parts in the surface shapes mutually coincide. This method, however, is associated with a drawback of generating a positional aberration in a direction perpendicular to the projected plane, since, in this method, it is difficult to detect the displacement of the three-dimensional object in the above-mentioned direction on the projected image.
FIG. 8A shows a projected image obtained by aligning two surface shapes on a projecting plane, and FIG. 8B shows an image on a different projecting plane, of the two surface shapes maintained in the same positional relationship as in FIG. 8A. From FIGS. 8A and 8B it will be understood that a positional aberration is generated between the two surface shapes, in a direction perpendicular to the projecting plane of FIG. 8A.
In order to resolve the above-mentioned drawback, there is proposed a method of simultaneously displaying images of the three-dimensional object onto different plural projecting planes and manually aligning the three-dimensional object with the help of these projected images. In this method, however, the operator is required to adjust the position of the surface shapes while watching the positional aberrations between the two surface shapes on the plural displayed images, and such operation is not only difficult but also cumbersome and time-consuming, and is extremely burdensome for the operator.
On the other hand, the efficiency of generation of the three-dimensional shape data can be apparently improved if plural three-dimensional shape data can be unified to generate new three-dimensional shape data. However, for the hierarchic three-dimensional shape data mentioned above, there has not been known a method for unifying plural three-dimensional shape data.
Also in unifying the shape data having an aperture, the unified shape data may contain a void portion by the influence of the aperture unless the shape data to be unified are appropriately positioned. Particularly in the hierarchic three-dimensional shape data, the shape data of each hierarchic level may vary delicately, so that the influence of the aperture may happen or not depending on the hierarchic level.